\begin{problem}{Коммивояжёр возвращается!}
{salesman.in}{salesman.out}{2 секунды}{256 мегабайт}

Коммивояжёр возвращается в систему Альфы Центавра!
Население системы с нетерпением ждёт его прибытия --- каждый
хочет приобрести что-нибудь с далёких планет!

Как обычно, коммивояжёр хочет минимизировать транспортные расходы.
Он выбирает начальную планету, прилетает туда на межгалактическом
корабле, после чего посещает все остальные планеты системы в порядке,
минимизирующем суммарную стоимость посещения, и на другом межгалактическом
корабле улетает обратно. Естественно, коммивояжёр не хочет летать ни на
какую планету дважды.

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

\InputFile

В системе Альфы Центавра $n$ планет. Это число записано в первой строке
входного файла  ($1\le n\le 19$). Следующие $n$ строк содержат по $n$
чисел каждая: $j$-ое число на $i$-ой из этих строк --- стоимость перемещения
$a_{ij}$ от $i$-ой планеты до $j$-ой. Числа в каждой строке разделены
пробелами. Числа $a_{ii}$ не несут полезной информации. Все числа
во входном файле положительны и не превосходят $10^8$.

\OutputFile

В первой строке выходного файла выведите минимальную суммарную стоимость
посещения всех планет. Во второй строке выведите $n$ чисел через пробел ---
номера планет системы в порядке их посещения. Если оптимальных маршрутов
несколько, можно вывести любой из них.

\Example

\begin{example}
\exmp{
3
8 1 6
3 5 7
4 9 2
}{
5
3 1 2
}%
\end{example}

\end{problem}
